package day0309

var res []string

func letterCombinations(digits string) []string {
	res = make([]string, 0)
	hmap := map[byte]string{
		'2': "abc",
		'3': "def",
		'4': "ghi",
		'5': "jkl",
		'6': "mno",
		'7': "pqrs",
		'8': "tuv",
		'9': "wxyz",
	}
	dfs(hmap, digits, 0, "")
	return res
}

func dfs(hmap map[byte]string, digits string, index int, str string) {
	if index == len(digits) {
		return
	}
	t := hmap[digits[index]]
	for i := 0; i < len(t); i++ {
		if len(str) == len(digits) {
			res = append(res, str)
		}
		dfs(hmap, digits, index+1, str+string(t[i]))
	}
}
